/**
 * 
 */
package leetCode;

import java.util.Stack;

/**
 * @author zhong
 *
 */
public class SumofSubarrayMinimums {
	public int sumSubarrayMins(int[] A) {
		Stack<Integer> stack = new Stack<>();
		int[] leftLessIndex = new int[A.length];
		initialNeg(leftLessIndex);
		for (int i = 0; i < A.length; i++) {
			while (!stack.isEmpty() && A[stack.peek()] > A[i]) {
				leftLessIndex[stack.pop()] = i;
			}
			stack.push(i);
		}

		stack.clear();
		int[] rightLessIndex = new int[A.length];
		initialNeg(rightLessIndex);
		for (int i = A.length - 1; i >= 0; i--) {
			while (!stack.isEmpty() && A[stack.peek()] > A[i]) {
				rightLessIndex[stack.pop()] = i;
			}
			stack.push(i);
		}
		int sum = 0;
		int mod = 1000000007;
		for (int i = 0; i < A.length; i++) {
			int q = rightLessIndex[i] == -1 ? 0 : (rightLessIndex[i] + 1);
			int p = leftLessIndex[i] == -1 ? A.length - 1 : (leftLessIndex[i] - 1);
			sum += (A[i] * (1 + p - q + (i - p) * (q - i)));
			sum %= mod;
		}
		return sum;
	}

	private void initialNeg(int[] rightGreaterIndex) {
		for (int i = 0; i < rightGreaterIndex.length; i++) {
			rightGreaterIndex[i] = -1;
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] A = { 3, 1, 2, 4 };
		System.out.println(new SumofSubarrayMinimums().sumSubarrayMins(A));
	}

}
